package linked_list

//206. 反转链表- 遍历法
//https://leetcode-cn.com/problems/reverse-linked-list/
func ReverseList(head *ListNode) *ListNode {
	curr := head
	var pre *ListNode
	var tmp *ListNode
	for curr != nil {
		//暂存下一个
		tmp = curr.Next

		//当前已遍历部分逆序
		curr.Next = pre
		pre = curr

		//指向下一个
		curr = tmp
	}
	return pre
}

//206. 反转链表-递归法
func ReverseList2(head *ListNode) *ListNode {
	return ReverseList2Helper(nil, head)
}

func ReverseList2Helper(pre, cur *ListNode) *ListNode {
	//递归终止条件
	if cur == nil {
		return pre
	}

	//本层递归需要做的: pre和cur逆序，得到新的pre和cur
	next := cur.Next
	cur.Next = pre
	pre = cur
	cur = next

	//继续处理下一个节点
	return ReverseList2Helper(pre, cur)
}
